package exec;

import java.util.*;

/**
 * @Description 给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0
 * @Date 2022/10/31 15:05
 * @Created by wangjun
 */
public class MaxProduct {

    /**
     * 功能描述: 给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0
     * <p>
     * 输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
     * 输出: 16
     * 解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。
     * <p>
     * <p>
     * 输入: words = ["a","ab","abc","d","cd","bcd","abcd"]
     * 输出: 4
     * 解释: 这两个单词为 "ab", "cd"。
     * <p>
     * <p>
     * 输入: words = ["a","aa","aaa","aaaa"]
     * 输出: 0
     * 解释: 不存在这样的两个单词。
     *
     * @Param: [words]
     * @Return: int
     */
    public static int maxProduct(String[] words) {
        if (words.length == 0) {
            return 0;
        }
        boolean flag = false;
        int result = 0;
        HashSet<Character> hashSet = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            hashSet.clear();
            for (char c : words[i].toCharArray()) {
                hashSet.add(c);
            }
            for (int j = i + 1; j < words.length; j++) {
                flag = false;
                for (char c1 : words[j].toCharArray()) {
                    if (hashSet.contains(c1)) {
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    System.out.print(words[i] + "===" + words[j] + "; count:" + words[i].length() * words[j].length());
                    System.out.println();
                    result = Math.max(words[i].length() * words[j].length(), result);
                }
            }
        }
        return result;
    }

    public static int maxProduct2(String[] words) {
        if (words.length == 0) {
            return 0;
        }
        boolean flag = false;
        int result = 0;
        for (int i = 0; i < words.length; i++) {
            HashSet<Character> set = new HashSet<>();
            for (char c : words[i].toCharArray()) {
                set.add(c);
            }
            for (int j = i + 1; j < words.length; j++) {
                flag = false;
                for (char c1 : words[j].toCharArray()) {
                    if (set.contains(c1)) {
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    result = Math.max(words[i].length() * words[j].length(), result);
                }
            }
        }
        return result;
    }

    public static int maxProduct3(String[] words) {
        if (words.length == 0) {
            return 0;
        }
        int result = 0;
        int[] masks = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                masks[i] = masks[i] | 1 << (word.charAt(j) - 'a');
            }
        }
        for (int i = 0; i < masks.length; i++) {
            for (int j = i + 1; j < masks.length; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    result = Math.max(words[i].length() * words[j].length(), result);
                }
            }
        }
        return result;
    }


    public static int maxPrduct(String[] words) {
        int result = 0;
        //暴力解法：每次遍历到一个新的字符串时候,把他所有字母添加到List里面,然后遍历后续的字符串.
        for (int i = 0; i < words.length - 1; i++) {
            HashSet<Character> temp = new HashSet<>();
            for (char c : words[i].toCharArray()) {
                temp.add(c);
            }
            for (int j = i + 1; j < words.length; j++)//遍历除了当前字符串以外的后续字符串
            {
                boolean isAdd = true;
                for (char c : words[j].toCharArray()) {
                    //如果在遍历后续字符串时候遍历到一个当前字符串存在的字符的话则标识为false然后遍历下一个后续字符串
                    if (temp.contains(c)) {
                        isAdd = false;
                        break;
                    }
                }
                if (isAdd) result = Math.max(words[i].length() * words[j].length(), result);//尝试更新最大值
            }
        }
        return result;
    }

    public static void main(String[] args) {
//        int maxProduct = maxProduct(new String[]{"abcw", "baz", "foo", "bar", "fxyz", "abcdef"});
//        int maxProduct = maxProduct(new String[]{"a","ab","abc","d","cd","bcd","abcd"});
        int maxProduct = maxProduct3(new String[]{"cdbbfebebafbefc", "ecbeaeddcce", "aefeeddafccaedafddd", "cbe", "ececca", "adcfdbdffcebfedadcb", "edbfadcecbebfee", "eabcb", "bdfedaedbaeacf", "faabafbbbefdea", "deccfdffacbebdefbfa", "ffdf", "fdbeabbec", "cbcfeedaf", "ecdbfdebbebffbbbb", "ebee", "cfcdcbcfdacbdaaebfef", "dafabedfa", "babbdfcc", "eadeafdbcdbbaefbbbbdc", "faabad", "eeeaecdbbacbedbaeabd", "acfa", "eaaafeb", "acef", "dccaccfffedaabefccead", "bacdbfe", "fdfdafaa", "bacecdff", "cfadccadfdabbdcdaec", "acbdfffdbcdfffbdbec", "afbcfefc", "facaacffccecfff", "af", "aedcddabdddfdeafabfd", "fafbfeacffbbbceebaedc", "aabbbabddcadadda", "eccca", "fcafbdfb", "ffdadaeaebedec", "ccfc", "efaed", "eebbb", "dcafccfbbdfbddcfbefb", "aaeeb", "fcdd", "ccccb", "ddebebfdcdbaaf", "beeeb", "edbfdabdcfb", "cacfbf", "bceacbdababbfca", "ffb", "fcba", "bdfedbaafebbffcefece", "bf", "dbfbeabcecffdbcc", "dccebefccbecf", "aaebfacdaaabfbcfacd", "cb", "edbbbfcdbefeabcfd", "daabdcbadccfeffafa", "cfafbcdfbdabfadddddff", "cbfd", "bcaa", "dffbfebffedc", "ebcbfbaeadbbdfcaa", "dcedebbcdfffabbac", "dbedacddcec", "badedda", "beeeaaffcdadbdecaddc", "dcdbcdbffeddcfea", "dedbdecbca", "cbecacdcfcdcfbfeebdda", "bebbacebbfacfbbbed", "dc", "cdddaedbfeaeebdbef", "accbbd", "bbafead", "dcfba", "efac", "ffce", "cfa", "bac", "bdfdfecccfeadeafedee", "eedddbefdaefbcbf", "acedbeadaedfcdffebea", "cc", "cffbeebdedfdbf", "fdeacddefadbdecbe", "ccccedafdbedaeeb", "cfafddadadcfdbdfb", "aadbbedecd", "cadeffaaffdcaeeefdfbf", "adcaaefbffdfaadedbbb", "cbeebfeeddcfd", "abfaaecdffbdfafe", "fccbbae", "cefdee", "cfdbfbabacafecc"});
        System.out.println(maxProduct);
    }
}
